One of the long-standing challenges in computing is dealing with deadlocks. A deadlock occurs if a set of entities exists such that each entity in the set is waiting for the release of at least one resource owned by another entity in the set. Entities capable of owning a resource are referred to herein as possessory entities. In the context of a database system, for example, entities include among other things, processes and transactions. A transaction is an atomic unit of work.
For example, a transaction T1 may seek exclusive ownership of resources R1 and R2. If R1 is available and R2 is currently exclusively owned by another transaction T2, then transaction T1 may acquire exclusive ownership of R1 but must wait for R2 to become available. A deadlock will occur if transaction T2 seeks ownership of R1, and T2 is suspended to wait for R1 without releasing R2. Because both T1 and T2 are waiting for each other, they are deadlocked.
Computer systems employ a variety of deadlock handling mechanisms (deadlock handlers) that detect deadlocks. The process of resolving the deadlock involves first determining if there is a deadlock and second determining how to resolve the deadlock. A couple of techniques for dealing with a deadlock include a wait-for graph technique and a time-out technique.
The wait-for graph technique detects deadlocks based on “cycles”. Specifically, after a process requests a resource, or waits more than threshold period of time for a resource, a wait-for graph may be generated and examined for any cycles. If any cycles are identified, then the deadlock detection mechanism has identified a potential deadlock. A resource that is part of the deadlock cycle is then selected for use in resolving the deadlock. The resource thus selected is referred to herein as the “victim resource” because the entity that possesses or is requesting the resource will typically incur a performance penalty when steps are taken to resolve the deadlock. Similarly, the entity that possesses or is requesting the victim resource is referred to herein as the “victim entity”. The term “victim” is used herein to refer to either the victim resource or the victim entity.
Typically, the victim resource is the resource, within the cycle, which is held by the entity whose request resulted in a deadlock. One way in which to resolve the deadlock is to cause the lock on the victim resource to be released. The lock on the victim resource may be released in a variety of ways. For example, when the victim entity is a transaction, canceling the request for the resource that resulted in deadlock status is coupled with a rollback, which results in the release of resources held by the transaction. The transaction may then attempt to re-acquire the resources and re-perform the steps that were rolled back. This re-performing of steps may be done automatically or initiated based on customer input.
A wait-for graph is a graph that shows what entities possess resources, and what entities are waiting on resources. In the figures, the term “WAITING” indicates that the entity is in a “wait state” waiting for a resource and therefore the entity is not “RUNNING”. Examples of wait-for graphs are shown in FIGS. 1a and 1b. FIG. 1a depicts the following scenario:
1) Entity 110 has resource R1;
2) Entity 120 has resource R2 and needs resource R1. So Entity 120 queues up behind Entity 110 and goes into a wait state, waiting for Entity 110 to finish using resource R1;
3) Entity 130 has resource R3 and needs resource R2. So Entity 130 queues up behind Entity 120 and goes into a wait state, waiting for Entity 120 to finish using resource R2;
4) Entity 140 has resource R4 and needs resource R3. So Entity 140 queues up behind Entity 130 and goes into a wait state, waiting for Entity 130 to finish using resource R3;
5) Entity 150 has resource R5 and needs resource R4; So Entity 150 queues up behind Entity 140 and goes into a wait state, waiting for Entity 140 to finish using resource R4;
6) Entity 160 has no resource but it needs resource R5; Since Entity 150 already has resource R5, Entity 160 queues up behind Entity 150, goes into a wait state, waiting for Entity 150 to finish using resource R5;
7) Entity 110 also needs resource R5; Entity 160 is already waiting for resource R5; So Entity 110 queues up behind Entity 160, goes into a wait state, waiting for Entity 160 to finish using R5.
Another way of depicting a wait-for graph is by having the nodes be the resources and the arrows be the possessory entities. FIG. 1b depicts such a graph where R1, R2, R3, R4, R5, R6, R7, R8 are resources and the arrows E1, E2, E3, R4, E5, E6, E7, E8 are possessory entities. The arrow points from the resource that the possessory entity is holding. The arrow points to the resource that the possessory entity is requesting. Therefore, in FIG. 1b: 
1) Entity E1 holds R1 and is requesting R2;
2) Entity E2 holds R2 and is requesting R3;
3) Entity E3 holds R3 and is requesting R4;
4) Entity E4 holds R4 and is requesting R1 and R5;
5) Entity E5 holds R5 and is requesting R6;
6) Entity E6 holds R6 and is requesting R7;
7) Entity E7 holds R7 and is requesting R8; and
8) Entity E8 holds R8 and is requesting R1.
A deadlock situation is depicted by the cycle of entities and resources in FIGS. 1a and 1b. All of the entities in FIGS. 1a and 1b are waiting for resources and none of these entities is relinquishing resources so that another entity may proceed. Something has to be done to break the cycle. In FIG. 1a, Entity 110 was the last entity to request a resource and this request resulted in the cycle, therefore the resources that Entity 110 is holding will arbitrarily be selected for release. The problem is that the resources Entity 110 is holding may not be good candidates for release.
Under the time-out technique, a possessory entity is presumed to be involved in a deadlock once the possessory entity waits a threshold period of time to obtain ownership of a resource. The time-out technique is less accurate in detecting deadlocks, since delays in obtaining ownership of a resource may result from many causes other than deadlock.
Unfortunately, selecting the resource victim to be either (1) the most recently requested resource involved in a deadlock cycle, or (2) the resource requested by an entity that “times out”, may result in significant overhead. For example, in either case, the victim entity could be a long-running transaction that is nearly complete. Where a victim entity is a transaction, it necessary to re-execute the entire transaction. Terminating such an entity is particularly wasteful when the deadlock could be broken in some other manner using minimal overhead.
Based on the foregoing, it is desirable to provide a more efficient method of breaking a detected deadlock.